import java.util.Arrays;

public class LeetCode581 {

    public static void main(String[] args) {
        int[] nums = {2, 6, 4, 8, 10, 9, 15};

        System.out.println(findUnsortedSubarray(nums));
    }

                static int MIN = -100005;
                static int MAX = 100005;
    private static int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int i = 0, j = n - 1;
        while (i < j && nums[i] <= nums[i + 1]) {
            i++;
        }
        while (i < j && nums[j] >= nums[j - 1]) {
            j--;
        }
        int l = i, r = j;
        int min = nums[i], max = nums[j];
        for (int k = l; k <= r; k++) {
            if (nums[k] < min) {
                while (i >= 0 && nums[i] > nums[k]) {
                    i--;
                }
                min = i >= 0 ? nums[i] : MIN;
            }
            if (nums[k] > max) {
                while (j < n && nums[j] < nums[k]) {
                    j++;
                }
                max = j < n ? nums[j] : MAX;
            }
        }
        return i == j ? 0 : (j - 1) - (i + 1) + 1;
    }

    public static int findUnsortedSubarray1(int[] nums) {
        int n = nums.length;
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int left = 0, right = n - 1;
        while (left <= right && nums[left] == arr[left]) {
            left++;
        }
        while (left <= right && nums[right] == arr[right]) {
            right--;
        }
        return right - left + 1;
    }

}
